1. Field of the Invention
The present invention relates generally to a method of generating a three-dimensional (3D) surface for a virtual display system. More particularly, the invention relates to a method of generating a 3D surface defined by a boundary of a 3D point cloud.
2. Description of the Related Art
Generating complex 3D surfaces is among the more computationally expensive tasks performed by contemporary virtual display systems such as personal computers (PCs) and gaming consoles. For example, a complex 3D surface may be composed of millions of tiny shapes that must be individually rendered in order to generate the surface, and rendering each of the shapes generally requires performing a large number of mathematical operations such as geometric transformations, coordinate transformations, viewing and clipping transformations, lighting, shading, and hidden surface removal, to name but a few. Because of the high computational cost associated with generating complex 3D surfaces, more efficient ways to perform 3D surface generation are constantly sought after.
One particular area where improved surface rendering techniques are needed is in real-time virtual display environments. In order to produce a realistically animated real-time display, surfaces typically need to be rendered at a rate of at least 25 frames per second. Unfortunately, the frame rate generally places a practical limitation on the complexity of surfaces that can be rendered. However, as the efficiency of rendering algorithms increases, the complexity of surfaces that can be rendered within a given frame rate increases accordingly.
One type of complex 3D surface that arises in real-time virtual display environments are surfaces defined by boundaries of 3D point clouds. The 3D point cloud may represent, for example, a collection of independent particles such as those constituting a fluid. The boundary of the particle collection is rendered to give the appearance of the surface of the fluid.
Perhaps the most popular way of rendering 3D surfaces defined by boundaries of 3D point clouds is a technique known as Marching Cubes. The Marching Cubes technique is well known, and hence a lengthy discussion thereof is not provided herein. Briefly, the Marching Cubes technique is performed by defining a 3D grid of cubes encompassing a 3D point cloud. Each of the cubes is then “marched through” and corners of the cubes are individually tested to determine whether they are inside or outside of a boundary of the 3D point cloud. Each cube is then replaced with an appropriate polygon depending on which of the cube's corners are inside and outside of the boundary.
The Marching Cubes technique has at least two problems when it comes to generating surfaces in a real-time display environment. The first problem is that it marches through the cubes in a view independent manner. Because many of the cubes may not actually be visible to a viewer in the display environment, compute cycles are unnecessary wasted by marching through the non-visible cubes. The second problem with the Marching Cubes technique is that it marches through a 3D dataset, even though the 3D surface produced thereby is generally rendered in 2D. This also adds unnecessary computational cost to generating the 3D surface.
Methods operating in screen space, e.g., ray tracing and point splatting, overcome these problems by rendering the 3D surface in a strictly view dependent manner. For example, in ray tracing, a ray is cast into a scene from each pixel in a display. The rays are then traced along reflected and refracted directions to yield scene details from the perspective of each pixel.
Unfortunately, the performance of screen space approaches such as ray tracing and point splatting tend to be even slower than that of the Marching Cubes technique. One reason is because these screen space approaches fail to make use of specialized graphics acceleration hardware such as the triangle rendering pipeline included in most contemporary virtual display systems.
Embodiments of the present invention overcome at least the above limitations of conventional approaches to provide more efficient ways of generating 3D surfaces defined by boundaries of 3D point clouds.